/*
 * Created by guoyh on Tue Dec 13 2022 11:41:57
 * leetcode NO. 
 */
#include <iostream>
#include<list>
#include <unordered_map>
#include<utility>
#include <gtest/gtest.h>
using namespace std;

class LRUCache{
private:
    int capacity;
    list<int> keyList;
    unordered_map<int, pair<int, list<int>::iterator>> keymap;
    void insert(int key, int value){
        keyList.push_back(key);
        keymap[key]  = make_pair(value, --keyList.end());
    }

public:
    LRUCache(int capacity){
        this->capacity = capacity;
    }

    int get(int key){
        auto it = keymap.find(key);
        if(it != keymap.end()){
            // 存在，调整list 中的位置，更新map 位置
            keyList.erase(it->second.second);
            keyList.push_back(key);
            keymap[key].second = --keyList.end();
            return keymap[key].first;
        }
        return -1;
    }

    void put(int key, int value){
        if(get(key) != -1){
            // 存在,调整list 顺序，更新keymap; 不需要调整 位置
            keymap[key].first = value;
            return;
        }else{
            // 不存在，直接插入

            if(keyList.size() > capacity){
                // 超出容量，list 尾部元素出来
                int k = keyList.front();
                keyList.pop_front();
                keymap.erase(k);
                insert(key, value);
            }else{
                insert(key, value);
            }
        }
    }
};

TEST(Mytest, get1){
    LRUCache* lrucache = new LRUCache(200);
    lrucache->put(1,1);
    EXPECT_EQ(lrucache->get(1), 1)<<"original";
    lrucache->put(1,2);
    EXPECT_EQ(lrucache->get(1), 2)<<"updated";
    int c = 200;
    while(c > 0){
        lrucache->put(c, c);
        c--;
    }
    EXPECT_EQ(lrucache->get(201), -1);

    EXPECT_EQ(lrucache->get(198), 198);
}

int add(int a, int b) {
    return a + b;
}

TEST(MyTest, AddTest) {
    EXPECT_EQ(add(1, 2), 3);
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
